package acwing_05;
import java.util.*;
import java.io.*;
public class _2_01背包问题_3滚动数组_carl版 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static int N = 1010;
	static int n,m;// 物品 容积
	static int dp[] = new int[N];
	static int v[] = new int[N];// 体积
	static int w[] = new int[N];//价值
	static StringTokenizer st;
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			v[i] = Integer.parseInt(st.nextToken());
			w[i] = Integer.parseInt(st.nextToken());
		}
		
		for(int i = 0; i < n; i++) { // 从物品0开始
			// 为了确保物品不被重复添加/状态被更新，这里从最后一个物品的容积开始计算(反序遍历
			// 如果从前面开始遍历，那么dp[j-v[i]]取到的数就可能是最新的j层循环更新过的，导致当前物品被重复添加
			// 并且只有容积大于等于物品体积，才能操作是否放该物品
			for(int j = m; j >= v[i]; j--) { 
				// 转换成一维数组只需要去掉[i-1]，其他的不变
				dp[j] = Math.max(dp[j], dp[j-v[i]] + w[i]);
			}
		}
		
		// 直接取最后一个元素的价值就是最大价值
		System.out.println(dp[m]);
	}
}
